package recursion_DynamicProgramming;

import java.util.Arrays;

//假设有排成一行的N个位置，记为1~N，N一定大于或等于2
//开始时机器人在其中的M位置上(M 一定是1~N 中的一个)
// 如果机器人来到1位置，那么下一步只能往右来到2位置;
// 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置
// 如果机器人来到中间位置，那么下一步可以往左走或者往右走
// 规定机器人必须走K步，最终能来到P位置P也是1~N中的一个)的方法有多少种
// 给定四个参数 N、M、K、P，返回方法数。
public class Task01 {
    public static void main(String[] args) {
//        System.out.println(process1(2, 4, 4, 4));
//        System.out.println(ways2(10, 2, 4, 10));
        System.out.println(ways3(4, 2, 4, 4));
    }

    /**
     * @param cur 机器人当前来到的位置
     * @param res 还有多少步要走
     * @param aim 目标
     * @param N   1到N位置
     * @return 返回机器人从 cur出发走过 res步后最终停在 aim的方法数 是多少种
     */
    public static int process1(int cur, int res, int aim, int N) {
        if (res == 0) {//走完了
            return cur == aim ? 1 : 0; //走完发现cur来到的位置等于最终位置
        }
        //还有步数要走
        if (cur == 1) { //1->2 等于2位置的方法数
            return process1(2, res - 1, aim, N);
        }
        if (cur == N) { //N-1
            return process1(N - 1, res - 1, aim, N);
        }
        //中间位置上 比如5位置等于 4位置+6位置的方法数
        return process1(cur - 1, res - 1, aim, N) + process1(cur + 1, res - 1, aim, N);

    }

    public static int ways2(int N, int start, int aim, int k) {
        //n+1*k+1 缓存表  如果等于-1 那么之前就没有算过
        int[][] dp = new int[N + 1][k + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(start, k, aim, N, dp);
    }

    //cur范围 1->N  res范围0—k步
    public static int process2(int cur, int res, int aim, int N, int[][] dp) {

        if (dp[cur][res] != -1) { //之前算过
            return dp[cur][res];
        }
        //之前没有算过
        int ans = 0;
        if (res == 0) {//走完了
            ans = cur == aim ? 1 : 0; //走完发现cur来到的位置等于最终位置
        } else if (cur == 1) {
            ans = process2(2, res - 1, aim, N, dp);
        } else if (cur == N) {
            ans = process2(N - 1, res - 1, aim, N, dp);

        } else {
            ans = process2(cur - 1, res - 1, aim, N, dp) + process2(cur + 1, res - 1, aim, N, dp);
        }
        dp[cur][res] = ans;
        return ans;
    }

    //动态规划
    public static int ways3(int N, int start, int aim, int k) {
        //n+1*k+1 缓存表  如果等于-1 那么之前就没有算过
        int[][] dp = new int[N + 1][k + 1];
        dp[aim][0]=1;

        for (int rest = 1; rest <=k; rest++) {
            dp[1][rest] = dp[2][rest - 1];
                for (int cur = 2; cur < N; cur++) {
                    dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
                }
            dp[N][rest] = dp[N - 1][rest - 1];
        }

        return dp[start][k];
    }


}
